#include "HashMap.h"
#include <iostream>

// 构造
HashMap::HashMap(int Size):size(Size)
{
    // 定义一个数组，数组里都是Node*型指针
    array = new Node *[size];
    // 对这些指针进行初始化
    for(int i = 0; i < size; i++)
    {
        array[i] = nullptr;
    }
}

// 析构
HashMap::~HashMap()
{
    // 遍历数组，每个数组元素又都是一条链表
    for(int i = 0; i < size; i++)
    {
        Node *travelPoint = array[i];
        while(travelPoint != nullptr)
        {
            Node *temp = travelPoint->next;
            delete travelPoint;
            travelPoint = temp;
        }
    }
    delete []array; 
}

// show
void HashMap::show()
{
    for(int i = 0; i < size; i++)
    {
        Node *travelPoint = array[i];
        while(travelPoint != nullptr)
        {
            std::cout<<"hash值:"<<Hash(travelPoint->key)<<" "
                     <<"key:"<<travelPoint->key<<" "
                     <<"value:"<<travelPoint->value<<" "<<std::endl;
            travelPoint = travelPoint->next;
        }
    }
}

// 根据分组来打印（只打印值）
void HashMap::showByGroup()
{
    for(int i = 0; i < size; i++)
    {
        Node *travelPoint = array[i];
        if(travelPoint == nullptr)
            continue;
        while(travelPoint != nullptr)
        {
            std::cout<<travelPoint->value<<" ";
            travelPoint = travelPoint->next;
        }
        std::cout<<std::endl;
    }
}

// 插入（键值对）
void HashMap::Insert(const std::string &key, const ElementType &element)
{
    // 构建一个节点
    Node *node = new Node(key, element);
    // 计算哈希值
    int index = Hash(key);
    node->next = array[index];
    array[index] = node;
}

// 查（根据key找value）
// 如果返回值，那就不能判断非法值，所以要返回指针
ElementType *HashMap::Get(const std::string &key)
{
    // 没有冲突
    Node *node = array[Hash(key)]; // O(1)
    // 有冲突
    while(node != nullptr) // O(n)
    {
        if(node->key == key)
            return &node->value;
        node = node->next;
    }
    return nullptr;
}

// 重载 []
ElementType &HashMap::operator[](const std::string & key)
{
    ElementType *data = Get(key);
    // 存在则返回
    if(data)
        return *data;
    // 不存在就新建
    else
    {
        Insert(key, "");
        return *Get(key);
    }
}

// 删除（根据键值删除节点）
void HashMap::Remove(const std::string &key)
{
    Node *node = array[Hash(key)]; // O(1)
    if(node == nullptr)
        return;
    if(node->key == key)
    {
        array[Hash(key)] = node->next;
        return;
    }
    while(node->next != nullptr) // O(n)
    {
        if(node->next->key == key)
        {
            Node *freeNode = node->next;
            node->next = freeNode->next;
            delete freeNode;
            return;
        }
        node = node->next;
    } 
}

// 哈希函数
int HashMap::Hash(const std::string &key)
{
    int hash = 0;
    // 把一个字符串每一个位置上的字符的ASCII码值加起来，再取余size，最终可以获得一个int，但这样的离散度不够
    // 不管是取余也好还是整除也好，素数都没有公约数，所以加入素数，可以有效提高离散特性，
    for(int i = 0; i < key.size(); i++)
    {
        // 把上一个ASCII码值求出来的和*31，再加上下一个字母的ASCII码值，再取余size，就得到下一个字母的哈希值
        hash = (hash * 31 + key[i]) % size; // 数据比较小可以*31，经验之谈
    }
    return hash;
}